package vip.meeet.algorithm.link;

import java.util.HashSet;



public class Num83 {

    public static void main(String[] args) {

        ListNode listNode = build("11233");
        print(listNode);
        print(deleteDuplicates(listNode));
    }

    public static ListNode deleteDuplicates(ListNode head) {
        if(head.next == null){
            return head;
        }
        HashSet<Integer> ids = new HashSet<>();
        ids.add(head.val);
        ListNode tmp = head.next;
        ListNode pre = head;
        do{
            boolean add = ids.add(tmp.val);
            if(add){
                pre.next = tmp;
                pre = tmp;
            }
            tmp = tmp.next;
        }while (tmp != null);
        if(pre != null && pre.next != null) {
            if (!ids.add(pre.next.val)) {
                pre.next = null;
            }
        }
        return head;
    }

    public static ListNode build(String num){
        ListNode first = new ListNode(Integer.parseInt(String.valueOf(num.charAt(num.length()-1))));
        ListNode tmp = first;
        for(int i=num.length()-2;i>=0;i--){
            ListNode cur = new ListNode(Integer.parseInt(String.valueOf(num.charAt(i))));
            tmp.next = cur;
            tmp = cur;
        }
        return first;
    }

    public static void print(ListNode node){
        StringBuilder sb = new StringBuilder();
        do{
            sb.append(node.val).append(" -> ");
            node = node.next;
        }while (node != null);
        System.out.println(sb.subSequence(0,sb.length() - 4));
    }


    public static class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
   }

}
